#include "Uri.h"

#include <string.h>
#include <fan-llvm/core/Core.h>
#include "ArgErr.h"
#include "Err.h"
#include "FanInt.h"
#include "File.h"
#include "IndexErr.h"
#include "List.h"
#include "Map.h"
#include "MimeType.h"
#include "NameErr.h"
#include "ParseErr.h"
#include "Range.h"
#include "Str.h"
#include "StrBuf.h"
#include "Type.h"
#include "UnsupportedErr.h"


#define kCharNone          0x00
#define kCharScheme        0x01
#define kCharUser          0x02
#define kCharHost          0x04
#define kCharPath          0x08
#define kCharQuery         0x10
#define kCharFrag          0x20

static uint8_t kCharMap[128];
static uint8_t kDelimEscMap[128];
static Bool kNameMap[128];
static Uri* kEmptyUri;
static Map* kEmptyQuery;
static Range* kParentRange;
static Str* kHttpStr;
static Str* kSlashStr;
static Str* kTrueStr;
static Obj kDotStr;
static Obj kDoubleDotStr;

static Uri* Uri_doDecode(Str* s, Bool decoding);
static List* Uri_doDecodePath(Str* pathStr, Int numSegs);
static Map* Uri_doDecodeQuery(Str* queryStr);
static Str* Uri_doEncode(Uri* self, Bool encoding);
static void Uri_doEncodeStr(StrBuf* buf, Str* str, Bool encoding, Int section);
static void Uri_doEncodeQueryStr(StrBuf* buf, Str* str);
static void Uri_addQueryParam(Map* map, Str* q, Int start, Int eq, Int end, Bool escaped);
static Str* Uri_toQueryStr(Str* q, Int start, Int end, Bool escaped);
static Uri* Uri_doGetRange(Uri* self, Range* r, Bool forcePathAbs);
static void Uri_doPlusPath(Uri* t, Uri* base, Uri* r);
static Str* Uri_substr(Str* s, Int start, Int end, Bool decoding, Int section);
static void Uri_percentEncodeChar(StrBuf* buf, Char c);
static Str* Uri_toPathStr(List* path, Bool isAbs, Bool isDir);
static void Uri_normalize(Uri* self);
static void Uri_normalizeHttp(Uri* self);
static void Uri_normalizePath(Uri* self);
static void Uri_normalizeQuery(Uri* self);

Type* Uri_classType = NULL;
VTable* Uri_classVTable = NULL;


/**********************************************
 *
 * Methods and fields
 *
 **********************************************/


/* Bool equals(Obj? that) */
Bool Uri_equals(Obj self, NullableObj that)
{
  if (!VAL_IS_NULL(that) && Obj_typeof(that) == Uri_classType)
  {
    Uri* uri1 = VAL_GET_REF(self);
    Uri* uri2 = VAL_GET_REF(that);
    return Str_equals(VAL_MAKE_REF(uri1->str), VAL_MAKE_REF(uri2->str));
  }
  return FALSE;
}


/* Int hash() */
Int Uri_hash(Obj self)
{
  Uri* uri = VAL_GET_REF(self);
  return Str_hash(VAL_MAKE_REF(uri->str));
}


/* Str toStr() */
Str* Uri_toStr(Obj self)
{
  Uri* uri = VAL_GET_REF(self);
  return uri->str;
}


/* Uri defVal */
Uri* Uri_defVal(void)
{
  return kEmptyUri;
}


/* Uri? fromStr(Str s, Bool checked) */
Uri* Uri_fromStr_1(Str* s)
{
  return Uri_fromStr(s, TRUE);
}


/* Uri? fromStr(Str s, Bool checked) */
Uri* Uri_fromStr(Str* s, Bool checked)
{
  ExceptionBlock block = exceptionBegin();
  if (block == ExceptionBlock_Try)
  {
    return Uri_doDecode(s, FALSE);
  }
  else if (block == ExceptionBlock_Catch)
  {
    Err* e = exceptionCatch();
    if (checked)
      exceptionThrow(ParseErr_newWithFormattedMsg("Invalid Uri: '%r'", Err_msg(e)));
  }
  exceptionEnd();
  return NULL;
}


/* Uri? decode(Str s, Bool checked) */
Uri* Uri_decode_1(Str* s)
{
  return Uri_decode(s, TRUE);
}


/* Uri? decode(Str s, Bool checked) */
Uri* Uri_decode(Str* s, Bool checked)
{
  ExceptionBlock block = exceptionBegin();
  if (block == ExceptionBlock_Try)
  {
    return Uri_doDecode(s, TRUE);
  }
  else if (block == ExceptionBlock_Catch)
  {
    Err* e = exceptionCatch();
    if (checked)
      exceptionThrow(ParseErr_newWithFormattedMsg("Invalid Uri: '%r'", Err_msg(e)));
  }
  exceptionEnd();
  return NULL;
}


/* [private] Uri doDecode(Str s, Bool decoding) */
static Uri* Uri_doDecode(Str* s, Bool decoding)
{
  Uri* uri = Uri_newUnitialized();
  Int len = s->len;
  Int pos = 0;

  // ==== Scheme ====

  // Scan the string from the beginning looking for either a
  // colon or any character which doesn't fit a valid scheme
  Bool hasUpper = FALSE;
  for (Int i = 0; i < len; i++)
  {
    Char c = s->buffer[i];
    Bool isScheme = (c < 128) ? (kCharMap[c] & kCharScheme) != 0 : FALSE;
    if (isScheme)
    {
      hasUpper |= ('A' <= c && c <= 'Z');
      continue;
    }
    if (c != ':')
      break;

    // At this point we have a scheme; if we detected
    // any upper case characters normalize to lowercase
    pos = i + 1;
    Str* scheme = Str_substr(s, 0, i);
    if (hasUpper)
      scheme = Str_lower(scheme);
    uri->scheme = scheme;
    break;
  }

  // ==== Authority ====

  // Authority must start with //
  if (pos + 1 < len && s->buffer[pos] == '/' && s->buffer[pos + 1] == '/')
  {
    // Find end of authority which is /, ?, #, or end of string;
    // while we're scanning look for @ and last colon which isn't
    // inside an [] IPv6 literal
    Int authStart = pos + 2;
    Int authEnd = len;
    Int at = -1;
    Int colon = -1;
    for (Int i = authStart; i < len; i++)
    {
      Char c = s->buffer[i];
      if (c == '/' || c == '?' || c == '#')
      {
        authEnd = i;
        break;
      }
      else if (c == '@' && at < 0)
      {
        at = i;
        colon = -1;
      }
      else if (c == ':')
        colon = i;
      else if (c == ']')
        colon = -1;
    }

    // Start with assumption that there is no userinfo or port
    Int hostStart = authStart;
    Int hostEnd = authEnd;

    // If we found an @ symbol, parse out userinfo
    if (at > 0)
    {
      uri->userInfo = Uri_substr(s, authStart, at, decoding, kCharUser);
      hostStart = at + 1;
    }

    // If we found an colon, parse out port
    if (colon > 0)
    {
      uri->port = Int_fromStr_1(Str_substr(s, colon + 1, authEnd));
      hostEnd = colon;
    }

    // Host is everything left in the authority
    uri->host = Uri_substr(s, hostStart, hostEnd, decoding, kCharHost);
    pos = authEnd;
  }

  // ==== Path ====

  // Scan the string looking '?' or '#' which ends the path
  // section; while we're scanning count the number of slashes
  Int pathStart = pos;
  Int pathEnd = len;
  Int numSegs = 1;
  Char prev = 0;
  for (Int i = pathStart; i < len; i++)
  {
    Char c = s->buffer[i];
    if (prev != '\\')
    {
      if (c == '?' || c == '#')
      {
        pathEnd = i;
        break;
      }
      if (i != pathStart && c == '/')
        numSegs++;
      prev = c;
    }
    else
      prev = (c != '\\') ? c : 0;
  }

  // We now have the complete path section
  uri->pathStr = Uri_substr(s, pathStart, pathEnd, decoding, kCharPath);
  uri->path = Uri_doDecodePath(uri->pathStr, numSegs);
  pos = pathEnd;

  // ==== Query ====

  if (pos < len && s->buffer[pos] == '?')
  {
    // Look for end of query which is # or end of string
    Int queryStart = pos + 1;
    Int queryEnd = len;
    prev = 0;
    for (Int i = queryStart; i < len; i++)
    {
      Char c = s->buffer[i];
      if (prev != '\\')
      {
        if (c == '#')
        {
          queryEnd = i;
          break;
        }
        prev = c;
      }
      else
        prev = (c != '\\') ? c : 0;
    }

    // We now have the complete query section
    uri->queryStr = Uri_substr(s, queryStart, queryEnd, decoding, kCharQuery);
    uri->query = Uri_doDecodeQuery(uri->queryStr);
    pos = queryEnd;
  }

  // ==== Frag ====

  if (pos < len  && s->buffer[pos] == '#')
    uri->frag = Uri_substr(s, pos + 1, len, decoding, kCharFrag);

  // === normalize ===

  Uri_normalize(uri);

  // if decoding, then we don't want to use original
  // str as Uri.str, so re-encode it
  uri->str = Uri_doEncode(uri, FALSE);

  return uri;
}


/* [private] Str[] doDecodePath(Str pathStr, Int numSegs) */
static List* Uri_doDecodePath(Str* pathStr, Int numSegs)
{
  // If pathStr is "/" then path is the empty list
  Int len = pathStr->len;
  if (len == 0 || (len == 1 && pathStr->buffer[0] == '/'))
    return Type_emptyList(Str_classType);

  // Check for trailing slash
  if (pathStr->buffer[len - 1] == '/')
  {
    numSegs--;
    len--;
  }

  // Parse the segments
  List* path = List_new(Str_classType, numSegs);
  Int segStart = 0;
  Char prev = 0;
  for (Int i = 0; i < pathStr->len; i++)
  {
    Char c = pathStr->buffer[i];
    if (prev != '\\')
    {
      if (c == '/')
      {
        if (i > 0)
          List_add(path, VAL_MAKE_REF(Str_substr(pathStr, segStart, i)));
        segStart = i + 1;
      }
      prev = c;
    }
    else
      prev = (c != '\\') ? c : 0;
  }
  if (segStart < len)
    List_add(path, VAL_MAKE_REF(Str_substr(pathStr, segStart, pathStr->len)));

  return List_ro(path);
}


/* [Str:Str] decodeQuery(Str s) */
Map* Uri_decodeQuery(Str* s)
{
  ExceptionBlock block = exceptionBegin();
  if (block == ExceptionBlock_Try)
  {
    return Uri_doDecodeQuery(Uri_substr(s, 0, s->len, TRUE, kCharQuery));
  }
  else if (block == ExceptionBlock_Catch)
  {
    Err* e = exceptionCatch();
    exceptionThrow(ArgErr_newWithFormattedMsg("Invalid Uri query: '%r'", Err_msg(e)));
  }
  exceptionEnd();
  return NULL;
}


/* [private] [Str:Str] doDecodeQuery(Str queryStr) */
static Map* Uri_doDecodeQuery(Str* queryStr)
{
  Map* map = Map_new(Str_classType, Str_classType);

  Int start = 0;
  Int eq = 0;
  Int len = queryStr->len;
  Char prev = 0;
  Bool escaped = FALSE;
  for (Int i = 0; i < len; i++)
  {
    Char ch = queryStr->buffer[i];
    if (prev != '\\')
    {
      if (ch == '=')
        eq = i;
      if (ch != '&' && ch != ';')
      {
        prev = ch;
        continue;
      }
    }
    else
    {
      escaped = TRUE;
      prev = (ch != '\\') ? ch : 0;
      continue;
    }

    if (start < i)
    {
      Uri_addQueryParam(map, queryStr, start, eq, i, escaped);
      escaped = FALSE;
    }

    start = eq = i + 1;
  }

  if (start < len)
    Uri_addQueryParam(map, queryStr, start, eq, len, escaped);

  return Map_ro(map);
}


/* [private] Void addQueryParam(Map map, Str q, Int start, Int eq, Int end, Bool escaped) */
static void Uri_addQueryParam(Map* map, Str* q, Int start, Int eq, Int end, Bool escaped)
{
  Str* key;
  Str* val;
  if (start == eq && q->buffer[start] != '=')
  {
    key = Uri_toQueryStr(q, start, end, escaped);
    val = kTrueStr;
  }
  else
  {
    key = Uri_toQueryStr(q, start, eq, escaped);
    val = Uri_toQueryStr(q, eq + 1, end, escaped);
  }

  Val dup = Map_get_1(map, VAL_MAKE_REF(key));
  if (!VAL_IS_NULL(dup))
    val = Str_newWithFormat("%r,%r", VAL_GET_REF(dup), val);
  Map_set(map, VAL_MAKE_REF(key), VAL_MAKE_REF(val));
}


/* [private] Str toQueryStr(Str q, Int start, Int end, Bool escaped) */
static Str* Uri_toQueryStr(Str* q, Int start, Int end, Bool escaped)
{
  if (!escaped)
    return Str_substr(q, start, end);
  StrBuf* s = StrBuf_new(end - start);
  Char prev = 0;
  for (Int i = start; i < end; i++)
  {
    Char c = q->buffer[i];
    if (c != '\\')
    {
      StrBuf_addChar(s, c);
      prev = c;
    }
    else
    {
      if (prev == '\\')
      {
        StrBuf_addChar(s, c);
        prev = 0;
      }
      else
        prev = c;
    }
  }
  return StrBuf_toStr(VAL_MAKE_REF(s));
}


/* Str encode() */
Str* Uri_encode(Uri* self)
{
  if (self->encoded == NULL)
    self->encoded = Uri_doEncode(self, TRUE);
  return self->encoded;
}


/* [private] Str doEncode(Bool encoding) */
static Str* Uri_doEncode(Uri* self, Bool encoding)
{
  StrBuf* buf = StrBuf_new(16);

  // Scheme
  if (self->scheme != NULL)
  {
    StrBuf_add(buf, VAL_MAKE_REF(self->scheme));
    StrBuf_addChar(buf, ':');
  }

  // Authority
  if (self->userInfo != NULL || self->host != NULL || !VAL_IS_NULL(self->port))
  {
    StrBuf_addChar(buf, '/');
    StrBuf_addChar(buf, '/');
    if (self->userInfo != NULL)
    {
      Uri_doEncodeStr(buf, self->userInfo, encoding, kCharUser);
      StrBuf_addChar(buf, '@');
    }
    if (self->host != NULL)
      Uri_doEncodeStr(buf, self->host, encoding, kCharHost);
    if (!VAL_IS_NULL(self->port))
    {
      StrBuf_addChar(buf, ':');
      StrBuf_add(buf, VAL_MAKE_REF(Int_toStr(self->port)));
    }
  }

  // Path
  if (self->pathStr != NULL)
    Uri_doEncodeStr(buf, self->pathStr, encoding, kCharPath);

  // Query
  if (self->queryStr != NULL)
  {
    StrBuf_addChar(buf, '?');
    Uri_doEncodeStr(buf, self->queryStr, encoding, kCharQuery);
  }

  // Frag
  if (self->frag != NULL)
  {
    StrBuf_addChar(buf, '#');
    Uri_doEncodeStr(buf, self->frag, encoding, kCharFrag);
  }

  return StrBuf_toStr(VAL_MAKE_REF(buf));
}


/* [private] void doEncodeStr(StrBuf buf, Str str, Bool encoding, Int section) */
static void Uri_doEncodeStr(StrBuf* buf, Str* str, Bool encoding, Int section)
{
  if (!encoding)
  {
    StrBuf_add(buf, VAL_MAKE_REF(str));
    return;
  }

  Char c = 0;
  Char prev;
  for (Int i = 0; i < str->len; i++)
  {
    prev = c;
    c = str->buffer[i];

    // Unreserved character
    if (c < 128 && (kCharMap[c] & section) != 0 && prev != '\\')
    {
      StrBuf_addChar(buf, c);
      continue;
    }

    // The backslash esc itself doesn't get encoded
    if (c == '\\' && prev != '\\')
      continue;

    // We have a reserved, escaped, or non-ASCII

    // Encode
    if (c == ' ' && section == kCharQuery)
      StrBuf_addChar(buf, '+');
    else
      Uri_percentEncodeChar(buf, c);

    // If we just encoded backslash, then it
    // doesn't escape the next char
    if (c == '\\')
      c = 0;
  }
}


/* Str encodeQuery([Str:Str] q) */
Str* Uri_encodeQuery(Map* q)
{
  StrBuf* buf = StrBuf_new(256);
  for (MapIterator* it = Map_iterator(q); it != NULL; it = Map_iteratorAdvance(it))
  {
    Str* key = VAL_GET_REF(it->key);
    Str* val = VAL_GET_REF(it->val);
    if (StrBuf_size(buf) > 0)
      StrBuf_addChar(buf, '&');
    Uri_doEncodeQueryStr(buf, key);
    StrBuf_addChar(buf, '=');
    Uri_doEncodeQueryStr(buf, val);
  }
  return StrBuf_toStr(VAL_MAKE_REF(buf));
}


/* [private] Void encodeQueryStr(StrBuf buf, Str str) */
static void Uri_doEncodeQueryStr(StrBuf* buf, Str* str)
{
  for (Int i = 0; i < str->len; i++)
  {
    Char c = str->buffer[i];
    if (c < 128 && (kCharMap[c] & kCharQuery) != 0 && (kDelimEscMap[c] & kCharQuery) == 0)
      StrBuf_addChar(buf, c);
    else
      Uri_percentEncodeChar(buf, c);
  }
}


/* Bool isName(Str name) */
Bool Uri_isName(Str* name)
{
  Int len = name->len;

  // Must be at least one character long
  if (len == 0)
    return FALSE;

  // Check for "." and ".."
  if (name->buffer[0] == '.' && len <= 2)
  {
    if (len == 1)
      return FALSE;
    if (name->buffer[1] == '.')
      return FALSE;
  }

  // Check that each char is unreserved
  for (Int i = 0; i < len; i++)
  {
    Char c = name->buffer[i];
    if (c < 128 && kNameMap[c])
      continue;
    return FALSE;
  }

  return TRUE;
}


/* Void checkName(Str name) */
void Uri_checkName(Str* name)
{
  if (!Uri_isName(name))
    exceptionThrow(NameErr_new(name, NULL));
}


/* Str toLocale() */
Str* Uri_toLocale(Uri* self)
{
  return self->str;
}


/* Bool isAbs() */
Bool Uri_isAbs(Uri* self)
{
  return (self->scheme != NULL);
}


/* Bool isRel() */
Bool Uri_isRel(Uri* self)
{
  return (self->scheme == NULL);
}


/* Bool isDir() */
Bool Uri_isDir(Uri* self)
{
  Str* p = self->pathStr;
  return (p != NULL && p->len > 0 && p->buffer[p->len - 1] == '/');
}


/* Str? scheme() */
Str* Uri_scheme(Uri* self)
{
  return self->scheme;
}


/* Str? auth() */
Str* Uri_auth(Uri* self)
{
  if (self->host == NULL)
    return NULL;
  if (VAL_IS_NULL(self->port))
  {
    if (self->userInfo == NULL)
      return self->host;
    else
      return Str_newWithFormat("%r@%r", self->userInfo, self->host);
  }
  else
  {
    if (self->userInfo == NULL)
      return Str_newWithFormat("%r:%i", self->host, VAL_GET_INT(self->port));
    else
      return Str_newWithFormat("%r@%r:%i", self->userInfo, self->host, VAL_GET_INT(self->port));
  }
}


/* Str? host() */
Str* Uri_host(Uri* self)
{
  return self->host;
}


/* Str? userInfo() */
Str* Uri_userInfo(Uri* self)
{
  return self->userInfo;
}


/* Int? port() */
NullableInt Uri_port(Uri* self)
{
  return self->port;
}


/* Str[] path() */
List* Uri_path(Uri* self)
{
  return self->path;
}


/* Str pathStr() */
Str* Uri_pathStr(Uri* self)
{
  return self->pathStr;
}


/* Bool isPathAbs() */
Bool Uri_isPathAbs(Uri* self)
{
  Str* p = self->pathStr;
  return (p != NULL && p->len > 0 && p->buffer[0] == '/');
}


/* Bool isPathOnly() */
Bool Uri_isPathOnly(Uri* self)
{
  return self->scheme == NULL && self->host == NULL && VAL_IS_NULL(self->port)
      && self->userInfo == NULL && self->queryStr == NULL && self->frag == NULL;
}


/* Str name() */
Str* Uri_name(Uri* self)
{
  if (List_isEmpty(self->path))
    return Str_defVal();
  else
    return VAL_GET_REF(List_last(self->path));
}


/* Str basename() */
Str* Uri_basename(Uri* self)
{
  Str* n = Uri_name(self);
  NullableInt dot = Str_rindexChar(n, '.');
  if (VAL_IS_NULL(dot))
    return n;
  if (VAL_GET_INT(dot) < 2 && (Str_equals(VAL_MAKE_REF(n), kDotStr) || Str_equals(VAL_MAKE_REF(n), kDoubleDotStr)))
    return n;
  return Str_substr(n, 0, VAL_GET_INT(dot));
}


/* Str? ext() */
Str* Uri_ext(Uri* self)
{
  Str* n = Uri_name(self);
  NullableInt dot = Str_rindexChar(n, '.');
  if (VAL_IS_NULL(dot))
    return NULL;
  if (VAL_GET_INT(dot) < 2 && (Str_equals(VAL_MAKE_REF(n), kDotStr) || Str_equals(VAL_MAKE_REF(n), kDoubleDotStr)))
    return NULL;
  return Str_substr(n, VAL_GET_INT(dot) + 1, n->len);
}


/* MimeType? mimeType() */
MimeType* Uri_mimeType(Uri* self)
{
  if (Uri_isDir(self))
    return MimeType_dir();
  Str* ext = Uri_ext(self);
  return (ext != NULL) ? MimeType_forExt(ext) : NULL;
}


/* [Str:Str] query() */
Map* Uri_query(Uri* self)
{
  return self->query;
}


/* Str? queryStr() */
Str* Uri_queryStr(Uri* self)
{
  return self->queryStr;
}


/* Str? frag() */
Str* Uri_frag(Uri* self)
{
  return self->frag;
}


/* Uri? parent() */
Uri* Uri_parent(Uri* self)
{
  // If no path bail
  if (List_isEmpty(self->path))
    return NULL;

  // If just a simple filename, then no parent
  if (List_size(self->path) == 1 && !Uri_isPathAbs(self) && !Uri_isDir(self))
    return NULL;

  // Use getRange
  return Uri_getRange(self, kParentRange);
}


/* Uri pathOnly() */
Uri* Uri_pathOnly(Uri* self)
{
  if (self->pathStr == NULL)
    exceptionThrow(Err_newWithFormattedMsg("Uri has no path: %r", self));

  if (Uri_isPathOnly(self))
    return self;

  Uri* uri = Uri_newUnitialized();
  uri->path = self->path;
  uri->pathStr = self->pathStr;
  uri->query = kEmptyQuery;
  uri->str = self->pathStr;
  return uri;
}


/* Uri getRange(Range r) */
Uri* Uri_getRange(Uri* self, Range* r)
{
  return Uri_doGetRange(self, r, FALSE);
}


/* Uri getRangeToPathAbs(Range r) */
Uri* Uri_getRangeToPathAbs(Uri* self, Range* r)
{
  return Uri_doGetRange(self, r, TRUE);
}


/* [private] Uri doGetRange(Range r, Bool forcePathAbs) */
static Uri* Uri_doGetRange(Uri* self, Range* r, Bool forcePathAbs)
{
  if (self->pathStr == NULL)
    exceptionThrow(Err_newWithFormattedMsg("Uri has no path: %r", self));

  Int size = List_size(self->path);
  Int s = Range_absStart(r, size);
  Int e = Range_absEnd(r, size);
  Int n = e - s + 1;
  if (n < 0)
    exceptionThrow(IndexErr_newWithRange(r));

  Bool head = (s == 0);
  Bool tail = (e == size  - 1);
  if (head && tail && (!forcePathAbs || Uri_isPathAbs(self)))
    return self;

  Uri* t = Uri_newUnitialized();
  t->path = List_ro(List_getRange(self->path, r));

  StrBuf* sb = StrBuf_new(self->pathStr->len);
  if ((head && Uri_isPathAbs(self)) || forcePathAbs)
    StrBuf_addChar(sb, '/');
  for (Int i = 0; i < List_size(t->path); i++)
  {
    if (i > 0)
      StrBuf_addChar(sb, '/');
    StrBuf_add(sb, List_get(t->path, i));
  }
  if (!List_isEmpty(t->path) && (!tail || Uri_isDir(self)))
    StrBuf_addChar(sb, '/');
  t->pathStr = StrBuf_toStr(VAL_MAKE_REF(sb));

  if (head)
  {
    t->scheme   = self->scheme;
    t->userInfo = self->userInfo;
    t->host     = self->host;
    t->port     = self->port;
  }

  if (tail)
  {
    t->queryStr = self->queryStr;
    t->query    = self->query;
    t->frag     = self->frag;
  }
  else
    t->query    = kEmptyQuery;

  if (!head && !tail)
    t->str = t->pathStr;
  else
    t->str = Uri_doEncode(t, FALSE);

  return t;
}


/* Uri plus(Uri toAppend) */
Uri* Uri_plus(Uri* self, Uri* r)
{
  // If r is more or equal as absolute as base, return r
  if (r->scheme != NULL)
    return r;
  if (r->host != NULL && self->scheme == NULL)
    return r;
  if (Uri_isPathAbs(r) && self->host != NULL)
    return r;

  // This algorithm is lifted straight from
  // RFC 3986 (5.2.2) Transform References;
  Uri* base = self;
  Uri* t = Uri_newUnitialized();
  if (r->host != NULL)
  {
    t->userInfo = r->userInfo;
    t->host = r->host;
    t->port = r->port;
    t->path = r->path;
    t->pathStr = r->pathStr;
    t->query = r->query;
    t->queryStr = r->queryStr;
  }
  else
  {
    if (r->pathStr == NULL || r->pathStr->len == 0)
    {
      t->path = base->path;
      t->pathStr = base->pathStr;
      if (r->queryStr != NULL)
      {
        t->query = r->query;
        t->queryStr = r->queryStr;
      }
      else
      {
        t->query = base->query;
        t->queryStr = base->queryStr;
      }
    }
    else
    {
      if (Str_startsWith(r->pathStr, kSlashStr))
      {
        t->path = r->path;
        t->pathStr = r->pathStr;
      }
      else
        Uri_doPlusPath(t, base, r);
      t->query = r->query;
      t->queryStr = r->queryStr;
    }
    t->userInfo = base->userInfo;
    t->host = base->host;
    t->port = base->port;
  }
  t->scheme = base->scheme;
  t->frag = r->frag;
  t->str = Uri_doEncode(t, FALSE);

  Uri_normalize(t);
  return t;
}


/* [private] Void doPlusPath(Uri t, Uri base, Uri r) */
static void Uri_doPlusPath(Uri* t, Uri* base, Uri* r)
{
  Bool baseIsAbs = Uri_isPathAbs(base);
  Bool baseIsDir = Uri_isDir(base);
  Bool rIsDir = Uri_isDir(r);
  List* rPath = r->path;
  Bool dotLast = FALSE;

  // Compute the target path taking into account whether
  // the base is a dir and any dot segments in relative ref
  List* tPath;
  if (List_isEmpty(base->path))
    tPath = r->path;
  else
  {
    tPath = List_rw(base->path);
    if (!baseIsDir)
      List_pop(tPath);
    for (Int i = 0; i < List_size(rPath); i++)
    {
      Str* rSeg = VAL_GET_REF(List_get(rPath, i));
      if (Str_equals(VAL_MAKE_REF(rSeg), kDotStr))
      {
        dotLast = TRUE;
        continue;
      }
      if (Str_equals(VAL_MAKE_REF(rSeg), kDoubleDotStr))
      {
        if (!List_isEmpty(tPath))
        {
          List_pop(tPath);
          dotLast = TRUE;
          continue;
        }
        if (baseIsAbs)
          continue;
      }
      List_add(tPath, VAL_MAKE_REF(rSeg));
      dotLast = FALSE;
    }
  }

  t->path = List_ro(tPath);
  t->pathStr = Uri_toPathStr(tPath, baseIsAbs, rIsDir || dotLast);
}


/* Uri plusName(Str name, Bool asDir) */
Uri* Uri_plusName_1(Uri* self, Str* name)
{
  return Uri_plusName(self, name, FALSE);
}


/* Uri plusName(Str name, Bool asDir) */
Uri* Uri_plusName(Uri* self, Str* name, Bool asDir)
{
  List* newPath = List_rw(self->path);
  if (!Uri_isDir(self))
    List_pop(newPath);
  List_add(newPath, VAL_MAKE_REF(name));

  Uri* t = Uri_newUnitialized();
  t->scheme   = self->scheme;
  t->userInfo = self->userInfo;
  t->host     = self->host;
  t->port     = self->port;
  t->query    = kEmptyQuery;
  t->queryStr = NULL;
  t->frag     = NULL;
  t->path     = List_ro(newPath);
  t->pathStr  = Uri_toPathStr(t->path, Uri_isPathAbs(self), asDir);
  t->str      = Uri_doEncode(t, FALSE);
  return t;
}


/* Uri plusSlash() */
Uri* Uri_plusSlash(Uri* self)
{
  if (Uri_isDir(self))
    return self;

  Uri* uri = Uri_newUnitialized();
  uri->scheme   = self->scheme;
  uri->userInfo = self->userInfo;
  uri->host     = self->host;
  uri->port     = self->port;
  uri->query    = self->query;
  uri->queryStr = self->queryStr;
  uri->frag     = self->frag;
  uri->path     = self->path;
  uri->pathStr  = Str_plus(self->frag, VAL_MAKE_REF(kSlashStr));
  uri->str      = Uri_doEncode(uri, FALSE);
  return uri;
}


/* Uri plusQuery([Str:Str]? query) */
Uri* Uri_plusQuery(Uri* self, Map* query)
{
  if (query == NULL || Map_isEmpty(query))
    return self;

  Map* merge = Map_setAll(Map_dup(self->query), query);

  StrBuf* s = StrBuf_new(256);
  for (MapIterator* it = Map_iterator(merge); it != NULL; it = Map_iteratorAdvance(it))
  {
    if (!StrBuf_isEmpty(s))
      StrBuf_addChar(s, '&');
    Uri_doEncodeQueryStr(s, VAL_GET_REF(it->key));
    StrBuf_addChar(s, '=');
    Uri_doEncodeQueryStr(s, VAL_GET_REF(it->val));
  }

  Uri* uri = Uri_newUnitialized();
  uri->scheme   = self->scheme;
  uri->userInfo = self->userInfo;
  uri->host     = self->host;
  uri->port     = self->port;
  uri->frag     = self->frag;
  uri->query    = Map_ro(merge);
  uri->queryStr = StrBuf_toStr(VAL_MAKE_REF(self->queryStr));
  uri->path     = self->path;
  uri->pathStr  = self->pathStr;
  uri->str      = Uri_doEncode(uri, FALSE);
  return uri;
}


/* Uri relTo(Uri base) */
Uri* Uri_relTo(Uri* self, Uri* base)
{
    /*if (!OpUtil.compareEQ(this.scheme,   base.scheme) ||
        !OpUtil.compareEQ(this.userInfo, base.userInfo) ||
        !OpUtil.compareEQ(this.host,     base.host) ||
        !OpUtil.compareEQ(this.port,     base.port))
      return this;

    // at this point we know we have the same scheme and auth, and
    // we're going to create a new URI which is a subset of this one
    Sections t = new Sections();
    t.query    = this.query;
    t.queryStr = this.queryStr;
    t.frag     = this.frag;

    // find divergence
    int d=0;
    int len = Math.min(this.path.sz(), base.path.sz());
    for (; d<len; ++d)
      if (!this.path.get(d).equals(base.path.get(d)))
        break;

    // if diverenge is at root, then no commonality
    if (d == 0)
    {
      // `/a/b/c`.relTo(`/`) should be `a/b/c`
      if (base.path.isEmpty() && this.pathStr.startsWith("/"))
      {
        t.path = this.path;
        t.pathStr = this.pathStr.substring(1);
      }
      else
      {
        t.path = this.path;
        t.pathStr = this.pathStr;
      }
    }

    // if paths are exactly the same
    else if (d == this.path.sz() && d == base.path.sz())
    {
      t.path = emptyPath();
      t.pathStr = "";
    }

    // create sub-path at divergence point
    else
    {
      // slice my path
      t.path = this.path.getRange(Range.makeInclusive(d, -1));

      // insert .. backup if needed
      int backup = base.path.sz() - d;
      if (!base.isDir()) backup--;
      while (backup-- > 0) t.path.insert(0L, "..");

      // format the new path string
      t.pathStr = toPathStr(false, t.path, this.isDir());
    }

    return new Uri(t);*/
}


/* Uri relToAuth() */
Uri* Uri_relToAuth(Uri* self)
{
    /*if (scheme == null && userInfo == null &&
        host == null && port == null)
      return this;

    Sections t = new Sections();
    t.path     = this.path;
    t.pathStr  = this.pathStr;
    t.query    = this.query;
    t.queryStr = this.queryStr;
    t.frag     = this.frag;
    return new Uri(t);*/
}


/* File toFile() */
File* Uri_toFile(Uri* self)
{
  return File_make_1(self);
}


/* Obj? get(Obj? base, Bool checked) */
NullableObj Uri_get_0(Uri* self)
{
  return Uri_get(self, VAL_NULL, TRUE);
}


/* Obj? get(Obj? base, Bool checked) */
NullableObj Uri_get_1(Uri* self, NullableObj base)
{
  return Uri_get(self, base, TRUE);
}


/* Obj? get(Obj? base, Bool checked) */
NullableObj Uri_get(Uri* self, NullableObj base, Bool checked)
{
  // TODO
  exceptionThrow(UnsupportedErr_newWithFormattedMsg("sys::Uri.get not implemented yet"));
}


/* Str toCode() */
Str* Uri_toCode(Uri* self)
{
  StrBuf* s = StrBuf_new(self->str->len + 4);
  StrBuf_addChar(s, '`');

  for (Int i = 0; i < self->str->len; i++)
  {
    Char c = self->str->buffer[i];
    switch (c)
    {
      case '\n':  StrBuf_addChar(s, '\\');  StrBuf_addChar(s, 'n');  break;
      case '\r':  StrBuf_addChar(s, '\\');  StrBuf_addChar(s, 'r');  break;
      case '\f':  StrBuf_addChar(s, '\\');  StrBuf_addChar(s, 'f');  break;
      case '\t':  StrBuf_addChar(s, '\\');  StrBuf_addChar(s, 't');  break;
      case '`':   StrBuf_addChar(s, '\\');  StrBuf_addChar(s, '`');  break;
      case '$':   StrBuf_addChar(s, '\\');  StrBuf_addChar(s, '$');  break;
      default:    StrBuf_addChar(s, '$');   break;
    }
  }

  StrBuf_addChar(s, '`');
  return StrBuf_toStr(VAL_MAKE_REF(s));
}


/* [private] Str substr(Str s, Int start, Int end, Bool decoding, Int section) */
static Str* Uri_substr(Str* s, Int start, Int end, Bool decoding, Int section)
{
  // TODO
}


/* [private] Void percentEncodeChar(StrBuf, Char c) */
static void Uri_percentEncodeChar(StrBuf* buf, Char c)
{
  // TODO
}


/* [private] Str toPathStr(Str[] path, Bool isAbs, Bool isDir) */
static Str* Uri_toPathStr(List* path, Bool isAbs, Bool isDir)
{
  StrBuf* buf = StrBuf_new(16);
  if (isAbs)
    StrBuf_addChar(buf, '/');
  for (Int i = 0; i < List_size(path); i++)
  {
    if (i > 0)
      StrBuf_addChar(buf, '/');
    StrBuf_add(buf, List_get(path, i));
  }
  if (isDir && (StrBuf_isEmpty(buf) || StrBuf_get(buf, StrBuf_size(buf) - 1) != '/'))
    StrBuf_addChar(buf, '/');
  return StrBuf_toStr(VAL_MAKE_REF(buf));
}


/* [private] Void normalize() */
static void Uri_normalize(Uri* self)
{
  Uri_normalizeHttp(self);
  Uri_normalizePath(self);
  Uri_normalizeQuery(self);
}


/* [private] Void normalizeHttp() */
static void Uri_normalizeHttp(Uri* self)
{
  if (self->scheme == NULL || Str_equals(VAL_MAKE_REF(self->scheme), VAL_MAKE_REF(kHttpStr)))
    return;

  // Port 80 -> null
  if (!VAL_IS_NULL(self->port) && VAL_GET_INT(self->port) == 80)
    self->port = VAL_NULL;

  // If path is "" -> "/"
  if (self->pathStr == NULL || self->pathStr->len == 0)
  {
    self->pathStr = kSlashStr;
    if (self->path == NULL)
      self->path = Type_emptyList(Str_classType);
  }
}

/* [private] Void normalizePath() */
static void Uri_normalizePath(Uri* self)
{
  if (self->path == NULL)
    return;

  Bool isAbs = Str_startsWith(self->pathStr, kSlashStr);
  Bool isDir = Str_endsWith(self->pathStr, kSlashStr);
  Bool dotLast = FALSE;
  Bool modified = FALSE;
  for (Int i = 0; i < List_size(self->path); i++)
  {
    Obj seg = List_get(self->path, i);
    if (Str_equals(seg, kDotStr) && (List_size(self->path) > 1 || self->host != NULL))
    {
      List_removeAt(self->path, i);
      modified = TRUE;
      dotLast = TRUE;
      i -= 1;
    }
    else if (Str_equals(seg, kDoubleDotStr) && i > 0 && !Str_equals(List_get(self->path, i - 1), kDoubleDotStr))
    {
      List_removeAt(self->path, i);
      List_removeAt(self->path, i - 1);
      modified = TRUE;
      dotLast = TRUE;
      i -= 2;
    }
    else
      dotLast = FALSE;
  }

  if (modified)
  {
    if (dotLast)
      isDir = TRUE;
    if (List_isEmpty(self->path) || Str_equals(List_last(self->path), kDoubleDotStr))
      isDir = FALSE;
    self->pathStr = Uri_toPathStr(self->path, isAbs, isDir);
  }
}


/* [private] Void normalizeQuery() */
static void Uri_normalizeQuery(Uri* self)
{
  if (self->query == NULL)
    self->query = kEmptyQuery;
}


/**********************************************
 *
 * Type-system functions
 *
 **********************************************/


Type* Uri_initType(void)
{
  if (Uri_classType == NULL)
  {
    Type* baseType = Obj_initType();
    VTable* vtable = Uri_initVTable();
    Type* type = Type_new("Uri", baseType, vtable, sizeof(Uri), sizeof(UriVTable));
    Type_registerMethodImplementation(type, "auth", Uri_auth, 0);
    Type_registerMethodImplementation(type, "basename", Uri_basename, 0);
    Type_registerMethodImplementation(type, "checkName", Uri_checkName, 1);
    Type_registerMethodImplementation(type, "decode", Uri_decode_1, 1);
    Type_registerMethodImplementation(type, "decode", Uri_decode, 2);
    Type_registerMethodImplementation(type, "decodeQuery", Uri_decodeQuery, 1);
    Type_registerMethodImplementation(type, "encode", Uri_encode, 0);
    Type_registerMethodImplementation(type, "encodeQuery", Uri_encodeQuery, 1);
    Type_registerMethodImplementation(type, "equals", Uri_equals, 1);
    Type_registerMethodImplementation(type, "ext", Uri_ext, 0);
    Type_registerMethodImplementation(type, "frag", Uri_frag, 0);
    Type_registerMethodImplementation(type, "fromStr", Uri_fromStr_1, 1);
    Type_registerMethodImplementation(type, "fromStr", Uri_fromStr, 2);
    Type_registerMethodImplementation(type, "get", Uri_get_0, 0);
    Type_registerMethodImplementation(type, "get", Uri_get_1, 1);
    Type_registerMethodImplementation(type, "get", Uri_get, 2);
    Type_registerMethodImplementation(type, "getRange", Uri_getRange, 1);
    Type_registerMethodImplementation(type, "getRangeToPathAbs", Uri_getRangeToPathAbs, 1);
    Type_registerMethodImplementation(type, "hash", Uri_hash, 0);
    Type_registerMethodImplementation(type, "host", Uri_host, 0);
    Type_registerMethodImplementation(type, "isAbs", Uri_isAbs, 0);
    Type_registerMethodImplementation(type, "isDir", Uri_isDir, 0);
    Type_registerMethodImplementation(type, "isName", Uri_isName, 1);
    Type_registerMethodImplementation(type, "isPathAbs", Uri_isPathAbs, 0);
    Type_registerMethodImplementation(type, "isPathOnly", Uri_isPathOnly, 0);
    Type_registerMethodImplementation(type, "isRel", Uri_isRel, 0);
    Type_registerMethodImplementation(type, "mimeType", Uri_mimeType, 0);
    Type_registerMethodImplementation(type, "name", Uri_name, 0);
    Type_registerMethodImplementation(type, "parent", Uri_parent, 0);
    Type_registerMethodImplementation(type, "path", Uri_path, 0);
    Type_registerMethodImplementation(type, "pathOnly", Uri_pathOnly, 0);
    Type_registerMethodImplementation(type, "pathStr", Uri_pathStr, 0);
    Type_registerMethodImplementation(type, "plus", Uri_plus, 1);
    Type_registerMethodImplementation(type, "plusName", Uri_plusName_1, 1);
    Type_registerMethodImplementation(type, "plusName", Uri_plusName, 2);
    Type_registerMethodImplementation(type, "plusQuery", Uri_plusQuery, 1);
    Type_registerMethodImplementation(type, "plusSlash", Uri_plusSlash, 0);
    Type_registerMethodImplementation(type, "port", Uri_port, 0);
    Type_registerMethodImplementation(type, "query", Uri_query, 0);
    Type_registerMethodImplementation(type, "queryStr", Uri_queryStr, 0);
    Type_registerMethodImplementation(type, "relTo", Uri_relTo, 1);
    Type_registerMethodImplementation(type, "relToAuth", Uri_relToAuth, 0);
    Type_registerMethodImplementation(type, "scheme", Uri_scheme, 0);
    Type_registerMethodImplementation(type, "toCode", Uri_toCode, 0);
    Type_registerMethodImplementation(type, "toFile", Uri_toFile, 0);
    Type_registerMethodImplementation(type, "toLocale", Uri_toLocale, 0);
    Type_registerMethodImplementation(type, "toStr", Uri_toStr, 0);
    Type_registerMethodImplementation(type, "userInfo", Uri_userInfo, 0);
    Type_registerFieldImplementation(type, "defVal", Uri_defVal, NULL);
    Uri_classType = type;
    Uri_initStatic();
  }
  return Uri_classType;
}


VTable* Uri_initVTable(void)
{
  if (Uri_classVTable == NULL)
  {
    VTable* vtable = memoryAlloc(sizeof(UriVTable));
    memcpy(vtable, Obj_initVTable(), sizeof(FanObjVTable));
    ((FanObjVTable*)vtable)->equals = Uri_equals;
    ((FanObjVTable*)vtable)->hash = Uri_hash;
    ((FanObjVTable*)vtable)->toStr = Uri_toStr;
    Uri_classVTable = vtable;
  }
  return Uri_classVTable;
}


void Uri_initStatic(void)
{
  kEmptyUri = Uri_fromStr(Str_defVal(), TRUE);
  kEmptyQuery = Map_ro(Map_new(Str_classType, Str_classType));
  kParentRange = Range_new(0, -2, FALSE);
  kHttpStr = Str_newFromCStr("http");
  kSlashStr = Str_newFromCStr("/");
  kTrueStr = Str_newFromCStr("true");
  kDotStr = VAL_MAKE_REF(Str_newFromCStr("."));
  kDoubleDotStr = VAL_MAKE_REF(Str_newFromCStr(".."));
}
